package com.since.algorithm.search;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Sincerity on 2020/5/16.
 * 描述：二分法查找算法 ,插值查找 (mid)自适应
 * <p>
 * <a>插值查找的mid计算公式 mis=left+(right-left)*(findValue-array[left])/(array[right]-array[left])</a>
 * <p>
 * 1. 二分法查找算法 {@link #binarySearch(int[], int, int, int)}
 * 2.查找多个目标索引 二分法 {@link #binarySearchResultList(int[], int, int, int)}
 * 3.插值查找(二分法的优化){@link #insertBinarySearch(int[], int, int, int)}
 * 3.插值查找多个目标索引{@link #insertBinarySearchResultList(int[], int, int, int)}
 */
class BinarySearch {

    public static void main(String[] args) {
        int[] array = {3, 12, 24, 34, 36, 38, 37, 55, 68, 75, 88};
//        List<Integer> index = binarySearchResultList(array, 0, array.length - 1, 36);
//        int index = binarySearch(array, 0, array.length - 1, 36);
        int index = insertBinarySearch(array, 0, array.length - 1, 36);
        System.out.print("24的元素下标是" + index);
    }

    /**
     * 二分法查找算法
     *
     * @param array     目标数组
     * @param left      左边索引
     * @param right     右边索引
     * @param findValue 查找的元素
     * @return 如果找到返元素在数组中的索引 反之没有找到-1
     */
    public static int binarySearch(int[] array, int left, int right, int findValue) {
        //没有找到想要的元素
        if (left > right) {
            return -1;
        }
        //中轴数索引
        int mid = (left + right) / 2;
        //中轴数
        int midValue = array[mid];
        //当需要查找的数大于中轴数 表示向右查找
        if (findValue > midValue) {
            return binarySearch(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return binarySearch(array, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }

    /**
     * 可以查找多个相同元素的位置 返回元素的集合
     *
     * @param array     目标数组
     * @param left      左边索引
     * @param right     右边索引
     * @param findValue 需要查找的目标值
     * @return 没有找到返回一个空集合 找到返回存放目标索引的集合
     */
    public static List<Integer> binarySearchResultList(int[] array, int left, int right, int findValue) {
        //没有找到想要的元素
        if (left > right) {
            return new ArrayList<>();
        }
        //中轴数索引
        int mid = (left + right) / 2;
        //中轴数
        int midValue = array[mid];
        //当需要查找的数大于中轴数 表示向右查找
        if (findValue > midValue) {
            return binarySearchResultList(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return binarySearchResultList(array, left, mid - 1, findValue);
        } else
            //左边有相同的值
            return getSameElement(array, findValue, mid);

    }

    /**
     * 插值查找 (二分法的优化)
     *
     * @param array     目标数组
     * @param left      左边索引
     * @param right     右边索引
     * @param findValue 需要查找的元素
     * @return 如果存在目标元素返回元素在数组中的索引 不存在返回-1
     */
    public static int insertBinarySearch(int[] array, int left, int right, int findValue) {
        //没有找到想要的元素
        if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {
            return -1;
        }
        //中轴数计算公式 mid =left +(right-left)*(find-arr[left])/(arr[right]-arr[left])
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);
        int midValue = array[mid];
        if (findValue > midValue) {
            return insertBinarySearch(array, mid + 1, right, findValue);
        } else if (findValue < midValue) {
            return insertBinarySearch(array, left, mid - 1, findValue);
        } else {
            return mid;
        }
    }

    /**
     * 查找数组中存在多个相同元素的下标
     *
     * @param array     目标数组
     * @param left      左边索引
     * @param right     右边索引
     * @param findValue 需要查找的元素
     * @return 数组中存在目标元素返回目标元素的索引 不存在返回一个空集合
     */
    public static List<Integer> insertBinarySearchResultList(int[] array, int left, int right, int findValue) {
        //没有找到想要的元素
        if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {
            return new ArrayList<>();
        }
        //中轴数计算公式 mid =left +(right-left)*(find-arr[left])/(arr[right]-arr[left])
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);
        int midValue = array[mid];
        if (findValue > midValue) {
            return insertBinarySearchResultList(array, mid + 1, right, findValue);
        } else //左边有相同的值
            if (findValue < midValue) {
                return insertBinarySearchResultList(array, left, mid - 1, findValue);
            } else return getSameElement(array, findValue, mid);
    }

    /**
     * 处理数组中存在多个相同值得情况
     *
     * @param array     目标数组
     * @param findValue 查找的数组元素
     * @param mid       数组的中轴下标
     * @return 返回一个存放目标数的集合
     */
    private static List<Integer> getSameElement(int[] array, int findValue, int mid) {
        List<Integer> result = new ArrayList<>();
        int temp = mid - 1;
        while (temp >= 0 && array[temp] == findValue) {
            result.add(temp);
            temp--;
        }
        result.add(mid);
        //右边
        temp = mid + 1;
        while (temp <= array.length && array[temp] == findValue) {
            result.add(temp);
            temp++;
        }
        return result;
    }
}
